package com.example.demo.arithmetic.datastructure.tree;

//给定一个整数数组，它表示BST(即 二叉搜索树 )的 先序遍历 ，构造树并返回其根。
//保证 对于给定的测试用例，总是有可能找到具有给定需求的二叉搜索树。
//二叉搜索树 是一棵二叉树，其中每个节点， Node.left 的任何后代的值 严格小于 Node.val ,
//Node.right 的任何后代的值 严格大于 Node.val。
//二叉树的 前序遍历 首先显示节点的值，然后遍历Node.left，最后遍历Node.right。

//输入：preorder = [8,5,1,7,10,12]
//输出：[8,5,10,1,7,null,12]
public class Leetcode1008_2 {
    public TreeNode bstFromPreorder(int[] preorder) {
        return insert(preorder, 0, preorder.length - 1);
    }

    // 分治思想
    private TreeNode insert(int[] preorder, int start, int end) {
        if (start > end) {
            return null;
        }
        // 8
        TreeNode root = new TreeNode(preorder[start]);
        int index = start + 1;
        //        while (index < preorder.length - 1) {
        //            if (preorder[index] > preorder[start]) {
        //                break;
        //            }
        //            index++;
        //        }
        while (index <= end && preorder[index] < preorder[start]) {
            index++;
        }
        // index = 4
        root.left = insert(preorder, start + 1, index - 1);
        root.right = insert(preorder, index, end);
        return root;
    }
}
